/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-06-24
 * Time: 21:30
 */
//牛客网:https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
    public void print(ListNode list){
        while(list!=null){
            System.out.print(list.val+" ");
            list=list.next;
        }
        System.out.println("");
    }
}
public class Test {
    public static ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return pHead;
        }
        ListNode bighead;
        ListNode biglast;
        ListNode bignode =new ListNode(0);
        bighead=biglast=bignode;
        ListNode smallhead;
        ListNode smalllast;
        ListNode smallnode=new ListNode(0);
        smallhead=smalllast=smallnode;
        while (pHead != null) {
            if (pHead.val < x) {
                smalllast.next=pHead;
                smalllast=pHead;
                pHead=pHead.next;
            }
            else{
                biglast.next=pHead;
                biglast=pHead;
                pHead=pHead.next;
            }
        }
        biglast.next=null;
        smalllast.next=bighead.next;
        return smallhead.next;
    }
    public static void main(String[] args) {
        ListNode list1=new ListNode(1);
        ListNode list2=new ListNode(11);
        ListNode list3=new ListNode(2);
        ListNode list4=new ListNode(12);
        ListNode list5=new ListNode(3);
        ListNode list6=new ListNode(13);
        list1.next=list2;
        list2.next=list3;
        list3.next=list4;
        list4.next=list5;
        list5.next=list6;
        ListNode list=partition(list1,10);
        list.print(list);

    }

}

